package demo.practice.binary_search;

public class P69 {

    public static void main(String[] args) {
        P69 p69 = new P69();
        System.out.println(p69.mySqrt(0));
    }

    public int mySqrt(int x) {//x为非负整数
        /*if (x < 4)
            return 1;
        if (x == 4)
            return 2;*/


        int min = 0;
        int max = x;
        while (min < max) {
            int mid = min + (max - min) / 2;
            if (mid * mid == x)
                return mid;

            //if (mid * mid > x) {//mid偏大， int 数据溢出
            if (mid != 0 && x / mid < mid) {

                max = mid - 1;
            } else {
                min = mid + 1;
            }
        }
        //if (min * min > x)  // int 数据溢出


        if (min != 0 && x / min < min)        // x/0
            return min - 1;
        else
            return min;
    }


}
